package com.yiwenup.leetcode.offer;

/**
 * https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/
 **/
public class No033 {
    /**
     * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
     * 内存消耗：35.9 MB, 在所有 Java 提交中击败了48.46%的用户
     */
    public boolean verifyPostorder(int[] postorder) {
        // (左子树)(右子树)根节点
        return recur(postorder, 0, postorder.length - 1);
    }

    private boolean recur(int[] postorder, int left, int right) {
        // 递归终止条件，遍历完成
        if (left >= right) return true;
        // 1、找到左右子树的分界点
        int tmp = left;
        while (postorder[tmp] < postorder[right]) tmp++;
        int middle = tmp;
        while (postorder[tmp] > postorder[right]) tmp++;
        // 2、本次是遍历完整个序列的 && 回溯左子树序列 && 回溯右子树序列
        return tmp == right && recur(postorder, left, middle - 1) && recur(postorder, middle, right - 1);
    }

}
